package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021-8-20.<br><br>
 *
 * 中等：旋转链表
 */
public class Topic61 {
    public static void main(String[] args) {
        Topic61 instance = new Topic61();

        int[] array = new int[] {1,2,3,4,5};
        ListNode head = Util.createList(array);
        Util.printList(instance.rotateRight(head, 2));

        array = new int[] {0,1,2};
        head = Util.createList(array);
        Util.printList(instance.rotateRight(head, 4));
    }

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) {
            return head;
        }

        ListNode start = new ListNode(0);
        start.next = head;

        ListNode low = start;
        ListNode fast = start;

        int i = 1;
        while (i <= k) {
            fast = fast.next;

            if(fast.next == null) {
                fast = start;
                k = k % i + i;
            }

            i++;
        }

        if(fast.next != null) {
            while (fast.next != null) {
                low = low.next;
                fast = fast.next;
            }

            fast.next = head;
            start.next = low.next;
            low.next = null;
        }

        return start.next;
    }

    public ListNode rotateRight2(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) {
            return head;
        }

        ListNode curr = head;
        int len = 0;

        while (curr.next != null) {
            curr = curr.next;
            len++;
        }

        len++;
        curr.next = head;

        int count = len - (k % len);
        curr = head;
        while (count-- > 1) {
            curr = curr.next;
        }

        ListNode newHead = curr.next;
        curr.next = null;

        return newHead;
    }
} 
